﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.OnlyQuantityModeling
{
    public class IterativeDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;

        public IterativeDynamicCoinChanger(IList<int> values, IList<double> weights = null)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0, _n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            var mem = new double[Q + 1];
            mem[0] = 0.0;
            for(int q = 1; q <= Q; q++)
            {
                mem[q] =
                    Enumerable.Range(0, _n).Where(i => _values[i] <= q).Select(i => mem[q - _values[i]] + _weights[i]).
                        DefaultIfEmpty(double.PositiveInfinity).Min();
            }
            return mem[Q];
        }

        #endregion
    }
}
